Sets, Relations and Languages

Basic definitions

• An alphabet($\mathrm{\Sigma }$) is a finite set of symbols.
• A string($w$) is a finite sequence of symbols from some alphabet.
• Length($|w|$) $|w|=\mathrm{\#}\mathrm{s}\mathrm{y}\mathrm{m}\mathrm{b}\mathrm{o}\mathrm{l}\mathrm{s}\mathrm{i}\mathrm{n}w$.
• Empty string $e$ with $|e|=0$
• ${\mathrm{\Sigma }}^i$ = the set of all strings of legnth i over $\mathrm{\Sigma }$.
• ${\mathrm{\Sigma }}^{+}={\cup }_{i\ge 1}{\mathrm{\Sigma }}^i$, ${\mathrm{\Sigma }}^{\ast }={\cup }_{i\ge 0}{\mathrm{\Sigma }}^i={\mathrm{\Sigma }}^{+}\cup \{e\}$.
• Any $L\subseteq {\mathrm{\Sigma }}^{\ast }$ is called a language over $\mathrm{\Sigma }$.

String operations

1. concatenation: $\because u=a_1\dots a_i,v=b_1\dots b_j\therefore w=uv=a_1\dots a_i{b}_1\dots b_j$
2. exponentation: $w^i=ww...w(\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s})$
3. reversal: $\because w=a_1\dots a_i\therefore w^R=a_i\dots a_1$